package com.uf;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import com.data.ConnectedEdge;
import com.data.Node;

/**
 * Created by IntelliJ IDEA. User: Bill Date: 07/05/11 Time: 10:18 PM Performs
 * union-find for a given input edge set
 * 
 * Tested at 15:48 Sunday. it gives you aa, ab, ac, ad, ....
 */
public class UnionFind {
	private Map<Node, Node> nodes = new HashMap<Node, Node>();

	public UnionFind(Set<ConnectedEdge> edges) {
		for (ConnectedEdge edge : edges) {
			System.out.println(edge);
			union(edge);
		}
	}

	public Set<ConnectedEdge> getUFEdges() {
		Set<ConnectedEdge> ufEdges = new HashSet<ConnectedEdge>();
		for (Node n : nodes.keySet()) {
			ufEdges.add(new ConnectedEdge(n.getParent(), n));
		}
		return ufEdges;
	}

	private void union(ConnectedEdge edge) {
		Node n1 = edge.getNode1();
		if (nodes.containsKey(n1)) {
			n1 = nodes.get(n1);
		}
		Node n1Root = find(n1);
		Node n2 = edge.getNode2();
		if (nodes.containsKey(n2)) {
			n2 = nodes.get(n2);
		}
		Node n2Root = find(n2);
		System.out.println(n2 + " has the root " + n2Root);
		System.out.println(n1 + " has the root " + n1Root);
		nodes.put(n1, n1);
		nodes.put(n2, n2);
		nodes.put(n1Root, n1Root);
		nodes.put(n2Root, n2Root);
		int result = n1Root.compareTo(n2Root);
		if (0 == result) {
			for (Node node : nodes.keySet()) {
				if (node.getParent().equals(n2) || node.getParent().equals(n1)) {
					node.setParent(n2Root);
				}
			}
			return;
		} else if (result < 0) {
			n2Root.setParent(n1Root);
			n2.setParent(n1Root);
			for (Node node : nodes.keySet()) {
				if (node.getParent().equals(n2Root)
						|| node.getParent().equals(n2)) {
					node.setParent(n1Root);
				}
			}
		} else {
			n1Root.setParent(n2Root);
			n1.setParent(n2Root);
			for (Node node : nodes.keySet()) {
				if (node.getParent().equals(n1Root)
						|| node.getParent().equals(n1)) {
					node.setParent(n2Root);
				}
			}
		}
	}

	private Node find(Node n) {
		if (n.getParent().equals(n)) {
			return n;
		}
		return find(n.getParent());
	}

	public static void main(String[] args) {
		Set<ConnectedEdge> edgesBeforeUF = new HashSet<ConnectedEdge>();
		edgesBeforeUF.add(new ConnectedEdge(new Node(0, 0), new Node(0, 1)));
		edgesBeforeUF.add(new ConnectedEdge(new Node(0, 2), new Node(1, 2)));
		edgesBeforeUF.add(new ConnectedEdge(new Node(0, 0), new Node(1, 0)));
		edgesBeforeUF.add(new ConnectedEdge(new Node(1, 0), new Node(1, 1)));
		edgesBeforeUF.add(new ConnectedEdge(new Node(1, 1), new Node(1, 2)));
		edgesBeforeUF.add(new ConnectedEdge(new Node(0, 1), new Node(0, 2)));
		edgesBeforeUF.add(new ConnectedEdge(new Node(0, 1), new Node(1, 1)));

		Set<ConnectedEdge> edges = (new UnionFind(edgesBeforeUF)).getUFEdges();
		System.out.println("UnionFind results: \n" + edges);
		System.out.println(edges.size());
	}
}
